| class FGAP_LIST{T} < $STR |
|---|
| **** | An array replacement for linked lists. The class `GAP_LIST{T}' is an array based list structure like `LIST{T}' but it supports insertions and deletions from the middle of the list as well as the end. This structure consists of an extensible array with a "gap" region in the middle. When an insertion or deletion is required, the gap is first moved to the proper location by moving elements around. Element access is by index and skips over the gap wherever it may lie. As long as most insertions and deletions are fairly close in location to the preceding one, the movement of elements accross the gap will not be extensive. Algorithms which are based on doubly linked lists often have a single pointer which moves up and down the list inserting and deleting elements as it moves. Such algorithms will also operate efficiently with gap lists. Sometimes this structure is refered to as a "double stack" since it may be viewed as two stack which approach one another. It has found wide use in text editors (such as GNU Emacs) and turns out to be much more efficient in practice than more obvious structures such as a linked list of strings for each line. |
| $STR | AREF{_} | COMPARE{_} |
| append(e: T): SAME |
|---|
| clear |
|---|
| **** | Clear the list. |
| create(a: $ELT{T}): SAME |
|---|
| create: SAME |
|---|
| **** | A new `GAP_LIST' with default `size=5'. |
| create_sized(n: INT): SAME |
|---|
| **** | A new `GAP_LIST' with `size=n'. |
| delete(i: INT): SAME |
|---|
| **** | Delete the `i'th element. |
| equals(e: $ARR{T}): BOOL |
|---|
| get(i: INT): T |
|---|
| **** | Retrieve the `i'th element. |
| has_ind(i: INT): BOOL |
|---|
| insert(i: INT, e: T): SAME |
|---|
| **** | Insert element `e' at location `i' pushing later elements forward. Elements may be inserted anywhere in the list or at the very end of the list |
| is_empty: BOOL |
|---|
| **** | True if `self' is empty. |
| replace(i: INT, e: T) |
|---|
| **** | Replace the `i'th element by `e'. |
| set(i: INT,val: T) |
|---|
| **** | Set the ith element |
| size: INT |
|---|
| **** | The total number of elements. |
| str: STR |
|---|
| **** | Prints out a string version of the flist of the components that are under $STR |
| elt!: T |
|---|
| set!(e: T) |
|---|
| attr gap_start,gap_size: INT; |
|---|
| **** | Start of gap and size of gap. |
| attr gap_start,gap_size: INT; |
|---|
| **** | Start of gap and size of gap. |
| attr gap_start,gap_size: INT; |
|---|
| **** | Start of gap and size of gap. |
| attr gap_start,gap_size: INT; |
|---|
| **** | Start of gap and size of gap. |
| move_gap(l: INT) |
|---|
| **** | Move the gap to start at `l'. Must have `l<=size'. |